use std::cmp::min;

const SALTS: [u32; 8] = [
    0x47b6137b, 0x4497a5af, 0x5b2b3f08, 0x5ac0c2d6,
    0x787f0bed, 0x4f636f90, 0x41ab5859, 0x591ccfd8
];

struct BloomFilter {
    table: Vec<u8>,
    size: usize,
    num_functions: usize,
}

impl BloomFilter {
    fn new(size: usize, num_functions: usize) -> Self {
        BloomFilter {
            table: vec![0; (size + 7) / 8],
            size,
            num_functions,
        }
    }

    fn insert(&mut self, value: &[u8]) {
        for i in 0..self.num_functions {
            let hash = murmur3(value, SALTS[i]);
            let index = hash as usize % self.size;
            self.set_bit(index);
        }
    }

    fn contains(&self, value: &[u8]) -> bool {
        for i in 0..self.num_functions {
            let hash = murmur3(value, SALTS[i]);
            let index = hash as usize % self.size;
            if !self.get_bit(index) {
                return false;
            }
        }
        true
    }

    fn union(&self, other: &BloomFilter) -> BloomFilter {
        assert_eq!(self.size, other.size);
        assert_eq!(self.num_functions, other.num_functions);

        let mut result = BloomFilter::new(self.size, self.num_functions);
        for i in 0..result.table.len() {
            result.table[i] = self.table[i] | other.table[i];
        }
        result
    }

    fn intersection(&self, other: &BloomFilter) -> BloomFilter {
        assert_eq!(self.size, other.size);
        assert_eq!(self.num_functions, other.num_functions);

        let mut result = BloomFilter::new(self.size, self.num_functions);
        for i in 0..result.table.len() {
            result.table[i] = self.table[i] & other.table[i];
        }
        result
    }

    fn set_bit(&mut self, index: usize) {
        let byte_index = index / 8;
        let bit_index = index % 8;
        self.table[byte_index] |= 1 << bit_index;
    }

    fn get_bit(&self, index: usize) -> bool {
        let byte_index = index / 8;
        let bit_index = index % 8;
        (self.table[byte_index] & (1 << bit_index)) != 0
    }
}

fn murmur3(data: &[u8], seed: u32) -> u32 {
    const C1: u32 = 0xcc9e2d51;
    const C2: u32 = 0x1b873593;

    let mut h1 = seed;
    let mut tail = 0u32;
    let nblocks = data.len() / 4;

    for i in 0..nblocks {
        let block = u32::from_le_bytes(data[i * 4..(i + 1) * 4].try_into().unwrap());
        h1 ^= hash_round(block, C1, C2);
        h1 = (h1 << 13) | (h1 >> 19); // Rotate left by 13 bits
        h1 = h1.wrapping_add(seed).wrapping_mul(5);
    }

    let remaining_bytes = data.len() % 4;
    if remaining_bytes == 3 {
        tail |= u32::from_le_bytes([data[data.len() - 3], data[data.len() - 2], data[data.len() - 1], 0]);
    } else if remaining_bytes == 2 {
        tail |= u32::from_le_bytes([data[data.len() - 2], data[data.len() - 1], 0, 0]);
    } else if remaining_bytes == 1 {
        tail |= u32::from_le_bytes([data[data.len() - 1], 0, 0, 0]);
    }

    h1 ^= hash_round(tail, C1, C2);
    h1 ^= (h1 >> 15) as u32;
    h1 = (h1.wrapping_mul(0x85ebca6b)).wrapping_add(seed);
    h1 ^= (h1 >> 13) as u32;
    h1 = (h1.wrapping_mul(0xc2b2ae35)).wrapping_add(seed);

    h1
}

fn hash_round(k: u32, c1: u32, c2: u32) -> u32 {
    let k1 = k.wrapping_mul(c1);
    let k1_rotated = (k1 << 15) | (k1 >> 17);
    k1_rotated.wrapping_mul(c2)
}
